package quantum.utils;

import org.apache.commons.math.complex.Complex;
import org.apache.commons.math.transform.FastFourierTransformer;

import quantum.state.QuantumState;

public class Utils {
	private static FastFourierTransformer transformer = new FastFourierTransformer();
	private static double TOLERANCE_ERROR = 0.0000005;
	
	public static int gcd(int a, int b) {
		int t;
		while(b != 0) {
			t = b;
			b = a % b;
			a = t;
		}
		
		return a;
	}
	
	public static QuantumState applyFourierTransform(QuantumState input) throws IllegalArgumentException {
		Complex[] amplitudes = adjust(input).toVector();
		amplitudes = transformer.transform2(amplitudes);
		return new QuantumState(amplitudes);
	}
	
	public static int powmod(int a, int b, int n) {
		int result = 1;
		while(b > 1) {
			result *= (result * a) % n;
		}
		
		return result;
	}
	
	public static int bestDenominator(double c, int qmax) {
		int a = (int)Math.floor(c);
		int[] B = new int[]{0, 1, 0};
		double r = c;
		
		while(true) {
			r = r - a;
			if( Math.abs(r) <= TOLERANCE_ERROR ) {
				break;
			}
			r = 1.0 / r;
			a = (int)Math.floor(r);
			
			B[2] = a * B[1] + B[0];
			if( B[2] > qmax )
				break;
			
			B[0] = B[1];
			B[1] = B[2];
		}
		
		return B[1];
	}
	
//	public static int bestDenominator(double c, int qmax) {
//		double y = c;
//		double z;
//		int q0 = 0;
//		int q1 = 1;
//		int q2 = 0;
//		while( true ) {
//			z = y - Math.floor(y);
//			if (z < 0.5 / (qmax*qmax)) { 
//				return(q1); 
//			}
//			if (z != 0) {
//				// Can't divide by 0.
//				y = 1 / z;
//			} else {
//				// this is broken if q1 == 0, but that should never happen.
//				return(q1);
//			}
//			q2 = (int)Math.floor(y) * q1 + q0;
//			if (q2 >= qmax) { 
//				return(q1); 
//			}
//			q0 = q1; 
//			q1 = q2;
//		}
//	}
	
	private static QuantumState adjust(QuantumState input) {
		QuantumState output = input;
		Complex[] amplitudes = input.toVector();
		int next_power_of_two = (int) Math.ceil(Math.log(amplitudes.length));
		int new_size = 1 << next_power_of_two;
		
		if( amplitudes.length < new_size ) {
			int i = 0;
			Complex[] new_amplitudes = new Complex[new_size];
			
			for( ; i<amplitudes.length ; i++) {
				new_amplitudes[i] = amplitudes[i];
			}
			
			for( ; i < new_amplitudes.length ; i++) {
				new_amplitudes[i] = Complex.ZERO;
			}
			
			output = new QuantumState(new_amplitudes);
		}
		
		return output;
	}
}
